package com.ls.linked_list;

import java.util.LinkedList;
import java.util.Stack;

public class SingleLinkedList {
    public static void main(String[] args) {
        HeroNode h1 = new HeroNode(1, "宋江", "");
        HeroNode h2 = new HeroNode(2, "卢俊义", "");
        HeroNode h3 = new HeroNode(3, "吴用", "");
        HeroNode h4 = new HeroNode(4, "林冲", "");
        HeroNode u0 = new HeroNode(2, "西瓜", "");
        HeroNode u1 = new HeroNode(10, "豆豆", "");
        SingleLinkedList linkedList = new SingleLinkedList();
        linkedList.add(h1);
        linkedList.add(h3);
        linkedList.add(h4);

        linkedList.addByOrder(h2);
        linkedList.addByOrder(h2);
        linkedList.update(u0);
        linkedList.update(u1);
        linkedList.delete(4);
        linkedList.delete(9);
        linkedList.show();


        int length = linkedList.getLength();
        System.out.println(length);

        HeroNode k = linkedList.findLastKNode(1);
        System.out.println(k);
        System.out.println("--------------");
        linkedList.reverse();
        linkedList.show();
        length = linkedList.getLength();
        System.out.println(length);
        linkedList.showInReverse();

    }

    //倒序打印
    public void showInReverse() {
        if (head.next == null) {
            System.out.println("不需要处理");
            return;
        }
        HeroNode cur = head.next;
        Stack<HeroNode> stack = new Stack<>();
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        while (!stack.empty()) {

            System.out.println(stack.pop());
        }

    }


    //单链表反转
    public void reverse() {
        //只有一个或者为空
        if (head.next == null || head.next.next == null) {
            System.out.println("不需要处理");
            return;
        }
        HeroNode newHead = new HeroNode(0, "", "");
        HeroNode newNext = null;
        HeroNode cur = head.next;
        HeroNode oldNext = null;
        while (cur != null) {

            newNext = newHead.next;
            oldNext = cur.next;
            newHead.next = cur;
            cur.next = newNext;
            cur = oldNext;
        }

        head = newHead;
    }

    //查找倒数第k个
    public HeroNode findLastKNode(int k) {
        int length = getLength();
        if (k > length || k <= 0) {
            System.out.println("不存在倒数第k个元素");
            return null;
        }
        int position = length - k;
        HeroNode temp = head.next;
        while (position-- != 0) {
            temp = temp.next;
        }

        return temp;
    }

    public int getLength() {

        if (head.next == null) {
            return 0;
        }
        int length = 0;
        HeroNode cur = head.next;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
        return length;


    }

    //初始化头节点,头节点存放具体数据
    private HeroNode head = new HeroNode(0, "", "");

    //当不考虑编号顺序时
    //1.找到当前链表的最后节点,
    //2.将next指向新节点
    public void add(HeroNode node) {

        HeroNode temp = head;
        //遍历链表找到最后
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = node;
    }

    //插入指定位置
    public void addByOrder(HeroNode node) {

        //因为头节点不能动,所以我们需要通过一个辅助指针来帮助找到添加位置
        HeroNode temp = head;
        boolean flag = false;//标志添加的编号是否存在
        //遍历链表找到最后
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no > node.no) {
                break;
            } else if (temp.next.no == node.no) {

                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.println("这个排名已存在" + node.no);
        } else {
            node.next = temp.next;
            temp.next = node;

        }

    }

    //修改节点信息
    public void update(HeroNode newNode) {

        if (head.next == null) {
            System.out.println("empty");
            return;
        }
        HeroNode temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == newNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = newNode.name;
            temp.nickName = newNode.nickName;
        } else {
            System.out.println("未找到节点");
        }
    }

    public void delete(int no) {
        if (head.next == null) {
            System.out.println("empty");
            return;
        }
        HeroNode temp = head;
        boolean flag = false;//是否找到删除节点的前一个
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            HeroNode deleteNode = temp.next;
            temp.next = temp.next.next;
            deleteNode.next = null;
        } else {
            System.out.println("未找到节点");
        }
    }

    //显示链表
    public void show() {
        if (head.next == null) {
            System.out.println("empty");
            return;
        }
        HeroNode temp = head.next;
        while (true) {
            //判断是否到链表最后
            if (temp == null) {
                break;
            }
            System.out.println(temp.toString());
            temp = temp.next;
        }
    }
}


//英雄节点
class HeroNode {
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}
